package org.example.list;

import java.nio.file.attribute.UserPrincipalNotFoundException;
import java.util.Iterator;

/**
 * @author carol
 */
public class CircleDoublyLinkedListSentinel implements Iterable<Integer> {


    /*
        哨兵即作为头也作为尾
         */
    private static class Node{
        Node prev;
        int value;
        Node next;

        public Node(Node prev,int value,Node next){
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node sentinel = new Node(null,-1,null);

    public CircleDoublyLinkedListSentinel(){
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

    public void addFirst(int value){
        Node prev = sentinel;

        Node next = sentinel.next;
        Node newNode = new Node(prev, value, next);

        prev.next = newNode;
        next.prev = newNode;
    }

     public void addLast(int value){
        //后继节点为哨兵
         Node prev = sentinel.prev;
         Node newNode = new Node(prev, value, sentinel);
         prev.next = newNode;
         sentinel.prev = newNode;
     }

     public int removeFirst(){
         Node removed = sentinel.next;
         if(removed == sentinel){
             throw new RuntimeException("size = 0");
         }
         sentinel.next = removed.next;
         removed.next.prev = sentinel;
         return removed.value;
     }

     public int removeLast(){
         Node removed = sentinel.prev;
         if(removed == sentinel){
             throw new RuntimeException("size = 0");
         }
         sentinel.prev = removed.prev;
         removed.prev.next = sentinel;
         return removed.value;
     }

     public void removeByValue(int value){
         Node removed = findByValue(value);
         if(removed==null){
             throw new RuntimeException("value not found");
         }
         Node prev = removed.prev;
         Node next = removed.next;

         prev.next = next;
         next.prev = prev;
     }



     private Node findByValue(int value){
        Node p = sentinel.next;
        while (p!=sentinel){
            if(p.value==value){
                return p;
            }
            p = p.next;
        }
        return null;
     }
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;
            @Override
            public boolean hasNext() {
                return p!= sentinel;
            }

            @Override
            public Integer next() {
                int result = p.value;
                p = p.next;
                return result;
            }
        };
    }


    public static void main(String[] args) {
        CircleDoublyLinkedListSentinel list = new CircleDoublyLinkedListSentinel();
        list.addFirst(0);
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.addLast(7);

        for (Integer i : list) {
            System.out.println(i);
        }
        System.out.println("removeFirst====>"+list.removeFirst());
        System.out.println("removeLast======>"+list.removeLast());
        list.removeByValue(4);
        list.removeByValue(6);
        for (Integer i : list) {
            System.out.println(i);
        }
    }
}
